'''
@author: Kevin Zhao
@data:Dec 31,2012 
@note:
heap-sort

Exercise 6.1~6.4
'''
import math
from custom_array import CustomArray

def left(index):
    return index * 2 + 1
def right(index):
    return index * 2 + 2

def exchange(A_index, B_index, array):
    temp = array[A_index]
    array[A_index] = array[B_index]
    array[B_index] = temp

#recursive version
def max_heapify(A, index):
    largest = index
    left_child_index = left(index)
    right_child_index = right(index)
    
    if left_child_index < A.get_heap_size() and A[left_child_index] > A[index]:
            if right_child_index >= A.get_heap_size() or A[left_child_index] > A[right_child_index]:
                largest = left_child_index
    if right_child_index < A.get_heap_size() and A[right_child_index] > A[index]:
            if left_child_index >= A.get_heap_size() or A[right_child_index] > A[left_child_index]:
                largest = right_child_index
    if largest != index:
        exchange(index, largest, A)
        max_heapify(A, largest)
    return

#iterative version
#def max_heapify(A, index):
#    largest = index
#    while 1:
#        left_child_index = left(index)
#        right_child_index = right(index)
#    
#        if left_child_index < A.get_heap_size() and A[left_child_index] > A[index]:
#            if right_child_index >= A.get_heap_size() or A[left_child_index] > A[right_child_index]:
#                largest = left_child_index
#        if right_child_index < A.get_heap_size() and A[right_child_index] > A[index]:
#            if left_child_index >= A.get_heap_size() or A[right_child_index] > A[left_child_index]:
#                largest = right_child_index
#        if largest != index:
#            exchange(index, largest, A)
#            index = largest
#        else:
#            break

def build_max_heap(A):
    A.set_heap_size(len(A))
    for i in range(int(math.floor(len(A) / 2)), -1, -1):
        max_heapify(A, i)
            
    
def heap_sort(A):
    build_max_heap(A)
    for i in range(len(A) - 1, 0, -1):
        exchange(i, 0, A)
        A.heap_size-=1
        max_heapify(A, 0)
        
        
        
a = CustomArray([5, 13, 2, 25, 7, 17, 20, 8, 4])
heap_sort(a)
print a.values

